package arithmetic.LeetCode._152MaximumProductSubarray;

/**
 * leetcode 152 题
 * <p>
 * Find the contiguous subarray within an array (containing at least one number) which has the largest product.
 * <p>
 * For example, given the array [2,3,-2,4],
 * the contiguous subarray [2,3] has the largest product = 6.
 *
 * @author zhangyanqi
 * @since 1.0 2018/1/6
 */
public class Solution {

    public int maxProduct(int[] nums) {
        int ans = Integer.MIN_VALUE;
        int start = 0;
        boolean has0 = false;
        for (int a = 0; a < nums.length; a++) {
            int product = 1;
            int minProductPositive = 1;
            int maxProductNegative =  Integer.MIN_VALUE;
            //第一位为0
            if (nums.length == 1) {
                return nums[0];
            }
            //中间到最后一位中有一位为0
            if (nums[a] == 0) {
                has0 = true;
                if (a == start) {
                    start = a + 1;
                    continue;
                }
                int[] ints = new int[a - start];
                System.arraycopy(nums, start, ints, 0, a - start);
                start = a + 1;
                for (int i = 0; i < ints.length; i++) {
                    product *= ints[i];
                    if (product > 0) {
                        if (product / minProductPositive > ans) {
                            ans = product / minProductPositive;
                        }
                        if (product < minProductPositive) {
                            minProductPositive = product;
                        }
                        continue;
                    }
                    if (product < 0) {
                        if (product / maxProductNegative > ans) {
                            ans = product / maxProductNegative;
                        }
                        if (product > maxProductNegative) {
                            maxProductNegative = product;
                        }
                        continue;
                    }
                }
            }
            //没有0
            if (a == nums.length - 1 && nums[a] != 0) {
                int[] ints = new int[a - start + 1];
                System.arraycopy(nums, start, ints, 0, a - start + 1);
                start = a + 1;
                for (int i = 0; i < ints.length; i++) {
                    product *= ints[i];
                    if (product > 0) {
                        if (product / minProductPositive > ans) {
                            ans = product / minProductPositive;
                        }
                        if (product < minProductPositive) {
                            minProductPositive = product;
                        }
                        continue;
                    }
                    if (product < 0) {
                        if (product / maxProductNegative > ans) {
                            ans = product / maxProductNegative;
                        }
                        if (product > maxProductNegative) {
                            maxProductNegative = product;
                        }
                        continue;
                    }
                }
            }
        }
        if (has0 && ans < 0) {
            return 0;
        }
        return ans;
    }
    public static void main(String[] args) {
        System.out.println(new Solution().maxProduct(new int[]{3, -1, 4}));
    }
}
